home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 11 / getmem.c < prev    next >
C/C++ Source or Header  |  1987-10-08  |  4KB  |  100 lines
  1. /*---------------------------------------------------------------------
  2.     getmem.c
  3.  
  4.     Implements low overhead memory management for nonrelocatable
  5.     blocks on the Macintosh.  This code is based on "Operating System
  6.     Design: The XINU Approach" by Douglas Comer (Prentice Hall, 1984.
  7.     Great book!)
  8.     
  9.     Motivation:
  10.     
  11.     The Macintosh Memory Manager is designed to use relocatable
  12.     blocks (i.e. pointers to pointers) for heap data structures.  In
  13.     order that relocatable blocks be free to move the Memory Manager
  14.     tries to keep nonrelocatable blocks (i.e. blocks referred to by
  15.     pointers) out of the way, i.e. in low mem.  To do this, when a program
  16.     asks for a nonrelocatable block the Memory Manager starts a linear
  17.     search for available space at the bottom of the heap.  In an
  18.     application such as a tree, where many thousands of small blocks are
  19.     needed, the linear search technique quickly dies.
  20.     
  21.     The code below bypasses this problem by requesting one large block at
  22.     the start of execution (i.e. when init_mem is called).  The function
  23.     getmem then maintains a pointer to the next available block.  Thus
  24.     any request for memory is satisfied immediately.  No search is needed.
  25.     The performance difference in the contour analysis is quite dramatic.
  26.  
  27.     The code below is quite simple but not flexible.  One notable
  28.     lack is for a routine to free memory.  Such a function is shown in
  29.     Comer's book.  Another limitation that only one block is used.
  30.     The functions can be extended to be able to add new blocks when it
  31.     needs additional space.
  32.     
  33.  
  34.     William May
  35.     303A Ridgefield Circle
  36.     Clinton, MA 01510
  37.  
  38.     created:    3/25/87        very primitive version, but works:
  39.                              one pool only created
  40.                             user has to guess the required space
  41.                              speed increase is dramatic, especially
  42.                              as the contour algorithm progresses (i.e.
  43.                              as the AVL tree gets quite large).
  44.   -------------------------------------------------------------------- */
  45.  
  46. #include <MemoryMgr.h>
  47. #include "mem.h"
  48.  
  49. struct mblock memlist;        /* head of free memory list */
  50. struct pool *plist;            /* head of pool list */
  51.  
  52. /*---------------------------------------------------------------------
  53.     init_mem creates a large memory pool, and initializes the necessary
  54.     data structures.
  55.   ---------------------------------------------------------------------*/
  56. int init_mem()
  57. {
  58.     plist = (struct pool *)NewPtr(sizeof(struct pool) + DEFSIZE);
  59.     
  60.     if (MemErr == noErr) {
  61.         plist->pnext = (struct pool *)0;
  62.         
  63.         memlist.mnext  = &(plist->firstblock);
  64.         (memlist.mnext)->mnext = (struct mblock *)0;
  65.         (memlist.mnext)->mlen  = (long)(DEFSIZE);
  66.     }
  67.     
  68.     return MemErr;
  69. }
  70.  
  71. /*---------------------------------------------------------------------
  72.     getmem allocates memory in the pool.  On successful completion
  73.      a pointer to the allocated space is returned to the caller.  Otherwise
  74.     a null pointer (0L) is returned.
  75.   ----------------------------------------------------------------------*/
  76. int *getmem(nbytes)
  77. unsigned long nbytes;
  78. {     
  79.      register struct mblock *p, *q, *leftover;
  80.  
  81.      if (nbytes == 0) {
  82.          return (int *)0;
  83.      }
  84.      
  85.      nbytes = (unsigned long)roundew(nbytes);
  86.      
  87.      for (q=&memlist, p=memlist.mnext; p != 0L; q=p, p=p->mnext)
  88.          if (p->mlen == nbytes) {
  89.              q->mnext = p->mnext;
  90.              return ((int *)p);
  91.          } else if (p->mlen > nbytes) {
  92.              leftover = (struct mblock *)((unsigned long)p + nbytes);
  93.              q->mnext = leftover;
  94.              leftover->mnext = p->mnext;
  95.              leftover->mlen = (long)(p->mlen - nbytes);
  96.              return ((int *)p);
  97.          }
  98.          
  99.       return ((int *)0);
  100. }